package week_six;

public class UniquePathsII_63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //状态f[i][j]从start到（i,j）的路径数
        //f[i][j] = f[i-1][j] + f[i][j-1];
        //边界f[0][0]=1， i=0或j=0,只有一个方向。
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] ans = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) ans[i][j] = 0;
                else if (i == 0 && j == 0) ans[i][j] = 1;
                else if (i == 0) ans[i][j] = ans[i][j - 1];
                else if (j == 0) ans[i][j] = ans[i - 1][j];
                else ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
            }
        }

        return ans[m - 1][n - 1];
    }

    int m, n;

    //时间超时，通过不了。
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        //递归 分治思想
        m = obstacleGrid.length;
        n = obstacleGrid[0].length;
        return countPaths(obstacleGrid, 0, 0);
    }

    private int countPaths(int[][] grid, int row, int col) {
        if (!isValidSquare(grid, row, col)) return 0;
        if (isAtEnd(grid, row, col)) {
            // System.out.println(row+" "+col+" :1");
            return 1;
        }
        return countPaths(grid, row + 1, col) + countPaths(grid, row, col + 1);
    }

    private boolean isValidSquare(int[][] grid, int row, int col) {
        return row >= 0 && row < m && col >= 0 && col < n && grid[row][col] != 1;
    }

    private boolean isAtEnd(int[][] grid, int row, int col) {
        return row == m - 1 && col == n - 1;
    }
}
